home *** CD-ROM | disk | FTP | other *** search
/ Resource for Source: C/C++ / Resource for Source - C-C++.iso / codelib7 / v_09_08 / 9n08022a < prev    next >
Encoding:
Text File  |  1995-11-01  |  10.4 KB  |  327 lines
  1.  
  2. /* --------------------------------------------------------------
  3.  
  4. CHANGE_NODE: The steps to change a selected node are:
  5.  
  6. A.  Complain if list empty.
  7.  
  8. B.  Get the node number from the user. Note that the first node in the 
  9.     list is number 0, then 1, 2, etc. The number of the node and the 
  10.     subscript it occupies in ary are NOT related even though they can 
  11.     be the same.
  12.  
  13. C.  Traverse list starting at the root node looking for the requested 
  14.     node. When it is found, display its data.
  15.  
  16. D.  Get the replacement data and update node.
  17.  
  18. -------------------------------------------------------------- */
  19.  
  20.         case CHANGE_NODE:
  21.  
  22. /*A*/           if (root_node == EOLIST) {
  23.                         printf("\n   List contains no nodes\n");
  24.                         break;
  25.                 }
  26.  
  27. /*B*/           while (1) {
  28.                         printf("\n   Enter node number: ");
  29.                         scanf("%d", &node);
  30.                         if (node >= 0 && node < nodes_in_use)
  31.                                 break;
  32.  
  33.                         printf("\n   No such node (%d) in list\n", node);
  34.                 }
  35.  
  36. /*C*/           j = root_node;          /* find nth node */
  37.                 for (i = 0; i < node; ++i)
  38.                         j = ary[j].fwd_ptr;
  39.  
  40. /*D*/           printf("\t[%d] => %3d\n", j, ary[j].value);
  41.                 printf("\n   Enter new value: ");
  42.                 scanf("%3d", &ary[j].value);
  43.                 printf("\n   Node changed");
  44.                 break;
  45.  
  46. /* --------------------------------------------------------------
  47.  
  48. SEARCH_FNODE: The steps to find the first node with a given value are:
  49.  
  50. A.  Complain if list empty.
  51.  
  52. B.  Get the required node value from user.
  53.  
  54. C.  Traverse list starting at the root node looking for the node with 
  55.     the requested value.  If it's found, display its data else say 
  56.     there is no such node.
  57.  
  58. -------------------------------------------------------------- */
  59.  
  60.         case SEARCH_FNODE:
  61.  
  62. /*A*/           if (root_node == EOLIST) {
  63.                         printf("\n   List contains no nodes\n");
  64.                         break;
  65.                 }
  66.  
  67. /*B*/           printf("\n   Enter search value: ");
  68.                 scanf("%d", &temp);
  69.  
  70. /*C*/           node = root_node;
  71.                 i = 0;
  72.                 while (node != EOLIST) {
  73.                         if (ary[node].value == temp) {
  74.                                 printf("\tValue %3d found in node %3d\n", 
  75.                                         temp, i);
  76.                                 goto found1;
  77.                         }
  78.                         node = ary[node].fwd_ptr;
  79.                         ++i;
  80.                 }
  81.  
  82.                 printf("\n   No such value (%d) in list\n", temp);
  83. found1:
  84.                 break;
  85.  
  86. /* --------------------------------------------------------------
  87.  
  88. SORT_NODES: The steps to sort the nodes in ascending order of value are:
  89.  
  90. A.  Complain if list empty.
  91.  
  92. B.  Perform a simple bubble sort.
  93.  
  94. -------------------------------------------------------------- */
  95.  
  96.         case SORT_NODES:
  97.  
  98. /*A*/           if (root_node == EOLIST) {
  99.                         printf("\n   List contains no nodes\n");
  100.                         break;
  101.                 }
  102.  
  103. /*B*/           for (i = nodes_in_use - 2; i >= 0; --i) {
  104.                         k = root_node;
  105.                         for (j = 0; j <= i; ++j) {
  106.                                 if (ary[k].value > ary[ary[k].fwd_ptr].value) {
  107.                                         temp = ary[k].value;
  108.                                         ary[k].value = ary[ary[k].fwd_ptr].value;
  109.                                         ary[ary[k].fwd_ptr].value = temp;
  110.                                 }
  111.                                 k = ary[k].fwd_ptr;
  112.                         }
  113.                 }
  114.  
  115.                 printf("\n   Nodes sorted");
  116.                 break;
  117.  
  118.  /* --------------------------------------------------------------
  119.  
  120. INSERT_NODE: The steps to insert a new node in front of an existing
  121. one are:
  122.  
  123. A.  Complain if list empty.
  124.  
  125. B.  Get a new free node from free node list.  If no more, get out.
  126.  
  127. C.  Get the node number from the user. Note that the first node in the 
  128.     list is number 0, then 1, 2, etc. The number of the node and the 
  129.     subscript it occupies in ary are NOT related even though they can 
  130.     be the same.
  131.  
  132. D.  Traverse list starting at the root node looking for the requested 
  133.     node. Then that when we find it we will have gone one node too 
  134.     many so we must keep track of the next-to-current code. 
  135.  
  136. E.  Have a new node so fill it with data.
  137.  
  138. F.  If this is to be the new first node, make it the root otherwise
  139.     update the forward pointer from the previous node to point to
  140.     this new node. Make the new node's forward pointer point to the 
  141.     node we are inserting ahead of.
  142.  
  143. -------------------------------------------------------------- */
  144.  
  145.         case INSERT_NODE:
  146.  
  147. /*A*/           if (root_node == EOLIST) {
  148.                         printf("\n   List contains no nodes\n");
  149.                         break;
  150.                 }
  151.  
  152. /*B*/           if ((new_node = get_free_node()) == EOLIST) {
  153.                         printf("\n   List is full\n");
  154.                         break;
  155.                 }
  156.  
  157. /*C*/           while (1) {
  158.                         printf("\n   Enter number of node to insert before: ");
  159.                         scanf("%d", &node);
  160.                         if (node >= 0 && node < nodes_in_use - 1) /* exclude new node */
  161.                                 break;
  162.  
  163.                         printf("\n   No such node (%d) in list\n", node);
  164.                 }
  165.  
  166. /*D*/           j = root_node;          /* find nth node */
  167.                 for (i = 0; i < node; ++i) {
  168.                         temp = j;
  169.                         j = ary[j].fwd_ptr;
  170.                 }
  171.  
  172. /*E*/           printf("\n   Enter new node's value: ");
  173.                 scanf("%3d", &ary[new_node].value);
  174.  
  175. /*F*/           if (root_node == j)
  176.                         root_node = new_node;
  177.                 else
  178.                         ary[temp].fwd_ptr = new_node;
  179.  
  180.                 ary[new_node].fwd_ptr = j;
  181.                 printf("\n   Node inserted");
  182.                 break;
  183.  
  184. /* --------------------------------------------------------------
  185.  
  186. REMOVE_NODE: The steps to remove a node are:
  187.  
  188. A.  Complain if list empty.
  189.  
  190. B.  Get the node number from the user. Note that the first node in the 
  191.     list is number 0, then 1, 2, etc. The number of the node and the 
  192.     subscript it occupies in ary are NOT related even though they can 
  193.     be the same.
  194.  
  195. C.  Traverse list starting at the root node looking for the requested 
  196.     node. Then that when we find it we will have gone one node too 
  197.     many so we must keep track of the next-to-current code. 
  198.  
  199. D.  If this is the last node make the tail EOLIST otherwise make tail 
  200.     point to the node ahead of this one.
  201.  
  202. E.  If this is the first node, make the root point to its successor 
  203.     node which, if that is EOLIST, is fine. Otherwise make it's 
  204.     predecessor point to the current node's successor.
  205.  
  206. F.  Free the node.
  207.  
  208. -------------------------------------------------------------- */
  209.  
  210.         case REMOVE_NODE:
  211.  
  212. /*A*/           if (root_node == EOLIST) {
  213.                         printf("\n   List contains no nodes\n");
  214.                         break;
  215.                 }
  216.  
  217. /*B*/           while (1) {
  218.                         printf("\n   Enter node number: ");
  219.                         scanf("%d", &node);
  220.                         if (node >= 0 && node < nodes_in_use)
  221.                                 break;
  222.  
  223.                         printf("\n   No such node (%d) in list\n", node);
  224.                 }
  225.  
  226. /*C*/           j = root_node;          /* find nth node */
  227.                 for (i = 0; i < node; ++i) {
  228.                         temp = j;
  229.                         j = ary[j].fwd_ptr;
  230.                 }
  231.  
  232. /*D*/           if (tail_node == j) {
  233.                         if (root_node == j)
  234.                                 tail_node = EOLIST;
  235.                         else
  236.                                 tail_node = temp;
  237.                 }
  238.  
  239. /*E*/           if (root_node == j)
  240.                         root_node = ary[j].fwd_ptr;
  241.                 else
  242.                         ary[temp].fwd_ptr = ary[j].fwd_ptr;
  243.  
  244. /*F*/           put_free_node(j);
  245.  
  246.                 printf("\n   Node removed");
  247.                 break;
  248.  
  249. /* ----------------------------------------------------------- */
  250.  
  251. The remaining function, that which frees up a node, follows:
  252.  
  253. /* --------------------------------------------------------------
  254.  
  255. FUNCTION put_free_node
  256.  
  257. Release an active node and add it to the front of the free list using
  258. the following steps:
  259.  
  260. A.  The newly freed node always points to the previous list head since 
  261.     we add to the front of the list.  If the list is currently empty,
  262.     free_node would be EOLIST and that's what we would want for the
  263.     new forward pointer anyway.
  264.  
  265. B.  Make the free_node point to the new head-of-list.
  266.  
  267. C.  Decrement the active node count.
  268.  
  269. -------------------------------------------------------------- */
  270.  
  271. void put_free_node(int node)
  272. {
  273.         ary[node].fwd_ptr = free_node;
  274.         free_node = node;
  275.         --nodes_in_use;
  276. }
  277.  
  278. /* ----------------------------------------------------------- */
  279.  
  280. The results of running this program with some test data are as follows:
  281.  
  282. Enter Action Code (? for help): t
  283.  
  284.    List nodes are as follows:
  285.         [0] => 350, fwd_ptr:   1
  286.         [1] => 200, fwd_ptr:   2
  287.         [2] => 500, fwd_ptr:  -1
  288.  
  289. Enter Action Code (? for help): i
  290.  
  291.    Enter number of node to insert before: 1
  292.  
  293.    Enter new node's value: 900
  294.  
  295.    Node inserted
  296. Enter Action Code (? for help): t
  297.  
  298.    List nodes are as follows:
  299.         [0] => 350, fwd_ptr:   3
  300.         [3] => 900, fwd_ptr:   1
  301.         [1] => 200, fwd_ptr:   2
  302.         [2] => 500, fwd_ptr:  -1
  303.  
  304. Enter Action Code (? for help): s
  305.  
  306.    Nodes sorted
  307. Enter Action Code (? for help): t
  308.  
  309.    List nodes are as follows:
  310.         [0] => 200, fwd_ptr:   3
  311.         [3] => 350, fwd_ptr:   1
  312.         [1] => 500, fwd_ptr:   2
  313.         [2] => 900, fwd_ptr:  -1
  314.  
  315. Enter Action Code (? for help): r
  316.  
  317.    Enter node number: 1
  318.  
  319.    Node removed
  320. Enter Action Code (? for help): t
  321.  
  322.    List nodes are as follows:
  323.         [0] => 200, fwd_ptr:   1
  324.         [1] => 500, fwd_ptr:   2
  325.         [2] => 900, fwd_ptr:  -1
  326.  
  327.